An operating system may implement at least one semaphore to determine an order in which processes are to be executed. In particular, the semaphore may be a variable or abstract data type which controls access to a common resource which is used by multiple applications in a parallel programming environment. A counting semaphore may utilize a counter system for a set of available resources. For example, the counting semaphore may include a count representing a maximum number of resources for processes of the operating system. For each process using a resource, the count may be decremented until no further processes may be allocated a resource. Upon a resource becoming free, the count may be incremented so that the counting semaphore may allocate the freed resource to an application.
Conventional semaphores for an operating system may utilize a lock or non-deterministic atomic operators. Conventional semaphores may use locks to isolate the semaphore for a process. However, the locks may result in deadlocks or other impasses that prevent the semaphore from being acquired. Furthermore, complex lock-free algorithms may be difficult to prove correct which may result in misallocation of resources, bypassing of processes queued for allocation of a resource, etc.
Many conventional computer systems have only non-deterministic atomic operators and are forced to use them. Non-deterministic atomic operators may also be difficult as they may remain ambiguous for an acquisition and/or releasing aspect of the semaphore which may also result in common problems associated with locks for the semaphore. Furthermore, the use of non-deterministic atomic operators make it impossible to impose an upper bound on the run-time of the system. For example, non-deterministic atomic operators may enable a limited number of higher level alternatives for a system to select but when the system ultimately selects a higher level alternative, further branching leads to lower level alternatives. Therefore, there are increasing amounts of paths for a system to take which increases the difficulty and complexity related to running the system. In another example, backtracking for failed alternatives also increases the difficulty and complexity of the system. In yet another example, with no backtracking, an iterative process may provide a deterministic result only but the number of loops that are executed are arbitrary.